ILP的16个高级概念——动态调度
AP SHANTHI博士
本模块的目标是讨论用于开发 ILP 的高级概念，并特别讨论动态调度的概念。
自大约 1985 年以来，所有处理器都使用流水线来重叠指令的执行并提高处理器的性能。指令之间的这种重叠称为指令级并行性，因为可以并行评估指令。有两种可分离的技术来利用 ILP：
• 动态并依赖于硬件来定位并行性
• 静态且更多地依赖软件
编译器采用静态技术来提高性能。主要使用硬件方法的处理器在这些优化之上使用其他技术来提高性能。动态的、硬件密集型方法主导了 PIII、P4 等处理器，甚至是 i3、i5 和 i7 等最新处理器。
我们知道，
管道 CPI = 理想管道 CPI + 结构停顿 + 数据危险停顿 + 控制危险停顿
在理想的管道CPI是由实现最大性能可达到的指标。
当我们考虑执行优化时，如果只考虑基本块，那么编译器和硬件都没有太多选择。一个基本块是一个直线代码序列，除了入口处没有分支进入，除了出口处没有分支出。由于平均动态分支频率为 15% 到 25%，我们通常只有 4 到 7 条指令在一对分支之间执行。此外，基本块中的指令很可能相互依赖。因此，基本块没有为利用 ILP 提供太多空间。为了获得实质性的性能增强，我们必须跨多个基本块利用 ILP。开发并行性的最简单方法是探索循环级并行性，以开发循环迭代之间的并行性。矢量架构是处理循环级并行的一种方式。否则，我们将不得不查看利用循环级并行性的动态或静态方法。常用的方法之一是循环展开，通过硬件动态分支预测，或由编译器使用静态分支预测静态地展开。
在执行此类优化时，硬件和软件都必须保持程序顺序。也就是说，如果顺序执行，一次一个，由原始源程序确定，指令的执行顺序应该保持不变。数据流，即产生结果的指令和使用结果的指令之间数据值的实际流动，应该得到维护。此外，只有当指令中使用的名称发生变化时，名称相关性中涉及的指令才能同时执行，以使这些指令不会发生冲突。这是通过寄存器重命名的概念完成的。这解决了寄存器的名称依赖性。这可以再次由编译器或硬件完成。保留异常行为，即
到目前为止，我们已经假设了按顺序执行的静态调度，并研究了使用各种技术处理上面讨论的所有问题。在本模块中，我们将讨论动态调度的必要性以及如何乱序执行指令。
动态调度是一种技术，其中硬件重新安排指令执行以减少停顿，同时保持数据流和异常行为。动态调度的优点是：
• 它处理在编译时依赖项未知的情况
–（例如，因为它们可能涉及内存引用）
• 它简化了编译器
• 它允许为一个管道编译的代码在不同的管道上高效运行
• 硬件推测，一种具有显着性能优势的技术，基于动态调度
在动态调度的流水线中，所有指令按顺序通过发布阶段；然而，它们可以在第二阶段停止或相互绕过，从而进入乱序执行。指令也将无序完成。
计分板是一种动态调度技术，用于在资源充足且没有数据依赖的情况下允许指令乱序执行。但是这种技术有一些缺点。Tomasulo 的算法是一种更复杂的技术，它比 Score boarding 有几个主要的改进。我们将在这里讨论 Tomasulo 的技术。
关键思想是允许具有可用操作数的指令执行，即使较早的指令尚未执行。例如，考虑以下指令序列：
DIV.D F0 , F2 , F4
ADD.D F10 , F0 , F8
SUB.D F12 , F8 , F14
DIV 指令是一条长延迟指令，ADD 依赖于它。所以，如果没有 DIV 完成，ADD 是无法执行的。但是，SUB 拥有所有可用的操作数，并且可以早于 ADD 执行。我们基本上是启用乱序执行，这将导致乱序完成。对于浮点指令，即使是按顺序执行，由于指令之间的延迟不同，我们也可能会出现乱序完成。现在，有了乱序执行，我们肯定会有乱序完成。我们还应该确保管道中不会因为动态调度而发生危险。
为了允许指令乱序执行，我们需要对解码阶段做一些改变。到目前为止，我们假设在解码阶段，MIPS 流水线解码指令并从寄存器文件中读取操作数。现在，通过动态调度，我们进行了更改以启用乱序执行。解码阶段或发布阶段仅对指令进行解码并检查结构性危险。之后，指令将等待直到没有数据危险，然后再读取操作数。这将使我们能够按顺序发出、乱序执行和乱序完成。例如，在我们之前的示例中，将按顺序发出 DIV、ADD 和 SUB。但是，由于真正的数据依赖性，ADD 将在发出后停止，但 SUB 将继续执行。
动态调度有一些缺点。他们是：
• 硬件复杂性大幅增加
• 使异常处理复杂化
• 乱序执行和乱序完成将产生WAR 和WAW 危险的可能性。战争危险并没有更早发生。
整个簿记是在硬件中完成的。硬件考虑一组称为指令窗口的指令，并尝试根据操作数的可用性重新安排这些指令的执行。硬件维护每条指令的状态并决定每条指令何时从一个阶段移动到另一个阶段 。动态调度程序在硬件中引入了寄存器重命名并消除了 WAW 和 WAR 危害。以下示例显示了如何完成寄存器重命名。F6 存在名称依赖性。
• 例子：
DIV.DF0,F2,F4
ADD.DF6,F0,F8
S.DF6,0(R1)
SUB.DF8,F10,F14
MUL.D F6,F10,F8
如下所示进行重命名后，只剩下 RAW 危险，可以严格排序。
• 例子：
DIV.DF0,F2,F4
添加.DS,F0,F8
S.DS,0(R1)
SUB.D T,F10,F14
MUL.D F6,F10,T
在 Tomasulo 的方法中，寄存器重命名由保留站 (RS) 提供。与每个功能单元相关联，我们有几个保留站。当发出指令时，为其分配一个保留站。保留站存储有关指令的信息并缓存操作数值（如果可用）。因此，一旦操作数可用（不一定涉及寄存器文件），保留站就获取并缓冲该操作数。这有助于避免 WAR 危险。如果操作数不可用，它会存储有关提供操作数的指令的信息。重命名是通过寄存器和保留站之间的映射完成的。当一个功能单元完成其操作时，结果在结果总线上广播，称为公共数据总线 (CDB)。该值被写入适当的寄存器以及等待该数据的保留站。当两条指令要修改同一个寄存器时，只有最后一个输出更新寄存器文件，从而处理 WAW 危险。因此，寄存器说明符与保留站一起重命名，保留站可能多于寄存器。负载用 和存储操作，我们使用加载和存储缓冲区，其中包含数据和地址，并像保留站一样工作。
下面列出了动态调度程序中的三个步骤：
• 问题
• 从 FIFO 队列中获取下一条指令
• 如果 RS 可用，则向 RS 发出具有操作数值的指令（如果可用）
• 如果 RS 不可用，它将成为结构性风险并且指令停止
• 如果没有发出较早的指令，则不能发出后续指令
• 如果操作数值不可用，则停止指令
• 执行
• 当操作数可用时，将其存储在任何等待它的保留站中
• 当所有操作数准备好后，发出执行指令
• 通过有效地址按程序顺序维护加载和存储
• 在按照程序顺序进行的所有分支都完成之前，不允许指令启动执行
• 写入结果
• 将 CDB 上的结果写入保留站并存储缓冲区
• 存储必须等到收到地址和值
动态调度器维护三种数据结构——保留站、保存将修改寄存器的指令的寄存器结果数据结构和指令状态数据结构。第三个更多是为了理解的目的。预留站组件如下图所示：
名称 - 识别预留站
Op——在单元中执行的操作（例如，+或-）
Vj、Vk - 源操作数的值
– 存储缓冲区有 V 字段，要存储的结果
Qj、Qk——产生源寄存器的保留站（要写入的值）
– Store buffers 只有 Qi for RS 产生结果 Busy——表示保留站或 FU 忙
寄存器结果状态——指示哪个功能单元将写入每个寄存器（如果存在）。当没有将写入该寄存器的未决指令时，它是空白的。指令状态给出指令窗口中每条指令的状态。所有三种数据结构如图 16.1 所示。
图 16.2 显示了 Tomasulo 的动态调度程序的组织结构。指令从指令队列中取出并发出。在发布阶段，指令被解码并分配一个 RS 条目。如果可用，RS 站也会缓冲操作数。否则，RS 条目在 Q 字段中标记未决 RS 值。结果通过 CDB 传递到适当的寄存器，如寄存器结果数据结构以及未决 RS 所指示。
还必须正确处理与内存位置相关的依赖关系。只要它们访问不同的地址，加载和存储就可以安全地无序完成。如果加载和存储访问相同的地址，则
加载在程序顺序存储之前，交换它们会导致 WAR 危害，或
存储在程序顺序中的加载之前，交换它们会导致 RAW 危害。
同样，将两个商店交换到同一地址会导致 WAW 危险。因此，为了确定是否可以在给定时间执行加载，处理器可以检查在程序顺序中加载之前的任何未完成存储是否与加载共享相同的数据存储器地址。类似地，存储必须等到没有未执行的加载或程序顺序较早的存储并共享相同的数据存储器地址。
总而言之，我们已经讨论了动态调度的重要性，其中硬件在运行时动态重组代码。我们已经讨论了 Tomasulo 的动态调度方法。已经详细说明了簿记完成和使用的各个步骤。
网页链接/支持材料
计算机组织与设计——硬件/软件接口，David A. Patterson 和 John L. Hennessy，第 4 版，Morgan Kaufmann，Elsevier，2009 年。
Computer Architecture – A Quantitative Approach，John L. Hennessy 和 David A. Patterson，第 5 版，Morgan Kaufmann，Elsevier，2011。